package com.yanceysong.codetop.s41_s50;

import java.util.Deque;
import java.util.LinkedList;

public class S49_Hard_32_最长有效括号 {
    /**
     * .S49_Hard_32_最长有效括号
     * .<p>
     * .LeetCode链接：<a href="https://leetcode.cn/problems/longest-valid-parentheses/">https://leetcode.cn/problems/longest-valid-parentheses/</a>
     * .<p>
     * .题目描述：
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
     * 左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。
     * .<p>
     * .示例：
     * .输入：s = "(()"            输出：2   解释：最长有效括号子串是 "()"
     * .输入：s = ")()())"         输出：4   解释：最长有效括号子串是 "()()"
     * .输入：s = ""               输出：0
     * .输入：s = "()(())"         输出：6   解释：整个字符串都是有效的
     * .输入：s = "())((())"       输出：4   解释：后半部分 "(())" 有效
     * .<p>
     * .核心标签：栈 / 动态规划 / 计数扫描 / 字符串
     * .可选思路：
     * .1. 栈：维护可能的起始位置（经典解法）
     * .2. 动态规划：dp[i] 表示以下标 i 结尾的最长有效括号长度
     * .3. 计数双向扫描：分别从左往右、右往左统计 '(' 和 ')' 数量匹配
     * .<p>
     * .本类实现三种方法，主方法采用栈实现，另外提供 dp 和 双向扫描 作为补充。
     * .<p>
     * .时间复杂度：O(n)（三种方法均为单/双线性遍历）
     * .空间复杂度：
     * .- 栈法：O(n) 最坏全部是 '(' 入栈
     * .- 动态规划：O(n) 需要 dp 数组
     * .- 双向扫描：O(1) 仅使用常数计数器
     * .<p>
     * .关键洞察（以栈法为例）：
     * .- 栈中保存的是“尚未匹配的左括号的索引”或者“最近一个不匹配位置的哨兵索引”
     * .- 初始压入 -1 作为基准，使得第一个合法区间长度可以被正确计算（i - (-1)）
     * .- 遇到 '(' 直接入栈索引；遇到 ')' 弹出一个索引尝试匹配
     * .- 若弹出后栈空，说明当前 ')' 没有匹配，压入其索引作为新的“非法起点”
     * .- 若弹出后栈不空，利用当前索引 i 与栈顶索引的差值计算有效区间长度
     * .<p>
     * .ASCII 栈行为示例：s = ")()())"（答案 4）
     * .初始：栈 [-1]
     * .i=0 ')': 弹出-1 → 栈空 → 压入0  栈 [0]
     * .i=1 '(': 压入1            栈 [0,1]
     * .i=2 ')': 弹出1  栈 [0] → 有效长度 = 2-0 = 2  max=2
     * .i=3 '(': 压入3            栈 [0,3]
     * .i=4 ')': 弹出3  栈 [0] → 有效长度 = 4-0 = 4  max=4
     * .i=5 ')': 弹出0  栈空 → 压入5  栈 [5]
     * .结束，答案 = 4
     * .<p>
     * .动态规划状态转移：
     * .- 若 s[i] == ')' 有可能形成有效结尾：
     * .  1) 如果 s[i-1] == '(' ： dp[i] = dp[i-2] + 2
     * .  2) 如果 s[i-1] == ')' ：找与 i 配对的 '(' 的位置 j = i - dp[i-1] - 1，若有效且 s[j]=='('，
     * .     dp[i] = dp[i-1] + 2 + (j-1>=0 ? dp[j-1] : 0)
     * .<p>
     * .双向扫描：
     * .- 从左往右：统计 leftCount 与 rightCount；若相等更新答案；rightCount>leftCount 清零
     * .- 从右往左：同理反向统计，处理形如 "(()" 这类左多右少的前缀
     * .<p>
     * .使用建议：
     * .- 只需结果：双向扫描 O(1) 空间最优
     * .- 需理解结构：栈法直观
     * .- 需后缀信息或扩展：DP 可回溯子问题
     */
    public int longestValidParentheses(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int maxLen = 0; // 记录最长有效括号长度
        Deque<Integer> openIndexStack = new LinkedList<>(); // 存储尚未匹配的 '(' 的索引；也可能存放最近的无效位置
        openIndexStack.push(-1); // 压入哨兵，便于计算起始于索引0的合法区间长度
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                // 左括号：压入其索引，等待未来的匹配
                openIndexStack.push(i);
            } else {
                // 右括号：尝试匹配一个左括号
                openIndexStack.pop();
                if (openIndexStack.isEmpty()) {
                    // 栈空：当前右括号无匹配，将它的索引作为新的“最近无效位置”
                    openIndexStack.push(i);
                } else {
                    // 栈不空：栈顶索引之后到当前 i 之间是一个有效区间
                    int currentValidLen = i - openIndexStack.peek();
                    if (currentValidLen > maxLen) {
                        maxLen = currentValidLen;
                    }
                }
            }
        }
        return maxLen;
    }

    /**
     * .动态规划解法
     * <p>
     * .@param s 输入字符串
     * .@return 最长有效括号长度
     */
    public int longestValidParenthesesDP(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[n]; // dp[i] 以 i 结尾的最长有效括号长度
        int max = 0;
        for (int i = 1; i < n; i++) { // i=0 无法形成有效括号
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = 2 + (i >= 2 ? dp[i - 2] : 0);
                } else { // s[i-1] == ')'
                    int prevLen = dp[i - 1];
                    int leftIndex = i - prevLen - 1; // 期望与当前 ')' 匹配的 '('
                    if (leftIndex >= 0 && s.charAt(leftIndex) == '(') {
                        dp[i] = prevLen + 2 + (leftIndex - 1 >= 0 ? dp[leftIndex - 1] : 0);
                    }
                }
                if (dp[i] > max) {
                    max = dp[i];
                }
            }
        }
        return max;
    }

    /**
     * .双向扫描（计数法）解法：常数空间
     * <p>
     * .@param s 输入字符串
     * .@return 最长有效括号长度
     */
    public int longestValidParenthesesScan(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int left = 0, right = 0, max = 0;
        // 左 -> 右：处理右括号多的场景
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') left++;
            else right++;
            if (left == right) {
                max = Math.max(max, 2 * right);
            } else if (right > left) { // 失衡，重置
                left = right = 0;
            }
        }
        // 右 -> 左：处理左括号多的场景
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') left++;
            else right++;
            if (left == right) {
                max = Math.max(max, 2 * left);
            } else if (left > right) { // 失衡，重置
                left = right = 0;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        S49_Hard_32_最长有效括号 solution = new S49_Hard_32_最长有效括号();
        System.out.println("=== 最长有效括号 测试开始 ===");

        // 统一测试三个实现，验证一致性
        testCase(solution, "", 0);
        testCase(solution, "()", 2);
        testCase(solution, "(()", 2);
        testCase(solution, ")()())", 4);
        testCase(solution, "()(())", 6);
        testCase(solution, "())((())", 4);
        testCase(solution, "((((((", 0);
        testCase(solution, "((()))())()", 8);
        testCase(solution, "()(()", 2);
        testCase(solution, "(()())", 6);
        testCase(solution, "()()()", 6);
        testCase(solution, "(()(()))", 8);
        testCase(solution, "())()", 2);

        System.out.println("\n=== 补充随机与边界测试 ===");
        // 边界：单字符
        testCase(solution, "(", 0);
        testCase(solution, ")", 0);

        // 交错结构
        testCase(solution, "())()", 2);
        testCase(solution, "())())", 2);
        testCase(solution, "()())()()", 4);

        System.out.println("\n=== 所有测试完成 ===");
    }

    private static void testCase(S49_Hard_32_最长有效括号 solution, String s, int expected) {
        int ansStack = solution.longestValidParentheses(s);
        int ansDP = solution.longestValidParenthesesDP(s);
        int ansScan = solution.longestValidParenthesesScan(s);
        boolean consistent = ansStack == ansDP && ansDP == ansScan;
        System.out.printf("输入: %-15s | 栈:%2d DP:%2d 扫描:%2d | 一致:%s | 期望:%2d %s\n",
                s, ansStack, ansDP, ansScan, consistent, expected,
                (ansStack == expected ? "✓" : "✗"));
        assert ansStack == expected : "栈法结果不符合期望";
        assert ansDP == expected : "DP结果不符合期望";
        assert ansScan == expected : "扫描法结果不符合期望";
    }
}
